public class Fib {
     //fib1 : O(log phi^n)
    public static long fib1(long n) {
        if (n < 2) {
            return n;
        } else {
            return fib1(n - 1) + fib1(n - 2);
        }
    }
    
 //fib3 : O(n)
    public static long fib2(long n) {
        long i = 1;
        long j = 0;
        long k;
        for (k = 1; k <= n; k++) {
            j = i + j;
            i = j - i;
        }
        return j;
    }

    
    //fib3 : O(log n)
    public static long fib3(long n) {
        int i=1, j=0, k=0, h=1, t=0;
        while (n>0) {
            if(n%2 == 1) {
                t = j*h;
                j = i*h + j*k + t;
                i = i*k + t;
            }
            t = h*h;
            h = 2*k*h + t;
            k = k*k + t;
            n = n/2;
        }
        return j;
    }
}